//135.分发糖果
//https://leetcode.cn/problems/candy
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int ret = 0;
        vector<int> v(n);
        //从左至右遍历 因为如果i>i-1那么i的糖必须比i-1多 又要最少颗 所以只能多一颗
        //因为会出现 1 2 3 4 5 这种情况 不能使用 ++v[i] 而是v[i] = v[i-1]+1
        //否则糖数计算异常
        //此时记录的只是右边的数量
        for (int i = 0; i < n; ++i)
        {
            if (i > 0 && ratings[i - 1] < ratings[i]) v[i] = v[i-1] + 1;
            else v[i] = 1;
        }
        int tmp = 1;
        //从右置左遍历 记录右边相对于自己可以获得的糖树 即 i>i+1时
        for (int i = n-1; i >= 0; --i)
        {
            if (i < n-1 && ratings[i + 1] < ratings[i]) ++tmp;
            else tmp = 1;

            ret += max(v[i],tmp);
        }
        return ret;
    }
};